/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#ifndef SkOpSegment_DEFINE
#define SkOpSegment_DEFINE

#include "include/core/SkPath.h"
#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/pathops/SkPathOps.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMath.h"
#include "src/base/SkArenaAlloc.h"
#include "src/pathops/SkOpAngle.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsBounds.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsCurve.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsTypes.h"

enum class SkOpRayDir;
class SkOpCoincidence;
class SkOpContour;
class SkPathWriter;
struct SkOpRayHit;
template <typename T> class SkTDArray;

class SkOpSegment {
public:
    bool operator < (const SkOpSegment &rh) const
    {
        return fBounds.fTop < rh.fBounds.fTop;
    }

    SkOpAngle *activeAngle(SkOpSpanBase *start, SkOpSpanBase **startPtr, SkOpSpanBase **endPtr, bool *done);
    SkOpAngle *activeAngleInner(SkOpSpanBase *start, SkOpSpanBase **startPtr, SkOpSpanBase **endPtr, bool *done);
    SkOpAngle *activeAngleOther(SkOpSpanBase *start, SkOpSpanBase **startPtr, SkOpSpanBase **endPtr, bool *done);
    bool activeOp(SkOpSpanBase *start, SkOpSpanBase *end, int xorMiMask, int xorSuMask, SkPathOp op);
    bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase *start, SkOpSpanBase *end, SkPathOp op, int *sumMiWinding,
        int *sumSuWinding);

    bool activeWinding(SkOpSpanBase *start, SkOpSpanBase *end);
    bool activeWinding(SkOpSpanBase *start, SkOpSpanBase *end, int *sumWinding);

    SkOpSegment *addConic(SkPoint pts[3], SkScalar weight, SkOpContour *parent)
    {
        init(pts, weight, parent, SkPath::kConic_Verb);
        SkDCurve curve;
        curve.fConic.set(pts, weight);
        curve.setConicBounds(pts, weight, 0, 1, &fBounds);
        return this;
    }

    SkOpSegment *addCubic(SkPoint pts[4], SkOpContour *parent)
    {
        init(pts, 1, parent, SkPath::kCubic_Verb);
        SkDCurve curve;
        curve.fCubic.set(pts);
        curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
        return this;
    }

    bool addCurveTo(const SkOpSpanBase *start, const SkOpSpanBase *end, SkPathWriter *path) const;

    SkOpAngle *addEndSpan()
    {
        SkOpAngle *angle = this->globalState()->allocator()->make<SkOpAngle>();
        angle->set(&fTail, fTail.prev());
        fTail.setFromAngle(angle);
        return angle;
    }

    bool addExpanded(double newT, const SkOpSpanBase *test, bool *startOver);

    SkOpSegment *addLine(SkPoint pts[2], SkOpContour *parent)
    {
        SkASSERT(pts[0] != pts[1]);
        init(pts, 1, parent, SkPath::kLine_Verb);
        fBounds.setBounds(pts, 2);
        return this;
    }

    SkOpPtT *addMissing(double t, SkOpSegment *opp, bool *allExist);

    SkOpAngle *addStartSpan()
    {
        SkOpAngle *angle = this->globalState()->allocator()->make<SkOpAngle>();
        angle->set(&fHead, fHead.next());
        fHead.setToAngle(angle);
        return angle;
    }

    SkOpSegment *addQuad(SkPoint pts[3], SkOpContour *parent)
    {
        init(pts, 1, parent, SkPath::kQuad_Verb);
        SkDCurve curve;
        curve.fQuad.set(pts);
        curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
        return this;
    }

    SkOpPtT *addT(double t);
    SkOpPtT *addT(double t, const SkPoint &pt);

    const SkPathOpsBounds &bounds() const
    {
        return fBounds;
    }

    void bumpCount()
    {
        ++fCount;
    }

    void calcAngles();
    SkOpSpanBase::Collapsed collapsed(double startT, double endT) const;
    static bool ComputeOneSum(const SkOpAngle *baseAngle, SkOpAngle *nextAngle, SkOpAngle::IncludeType);
    static bool ComputeOneSumReverse(SkOpAngle *baseAngle, SkOpAngle *nextAngle, SkOpAngle::IncludeType);
    int computeSum(SkOpSpanBase *start, SkOpSpanBase *end, SkOpAngle::IncludeType includeType);

    void clearAll();
    void clearOne(SkOpSpan *span);
    static void ClearVisited(SkOpSpanBase *span);
    bool contains(double t) const;

    SkOpContour *contour() const
    {
        return fContour;
    }

    int count() const
    {
        return fCount;
    }

    void debugAddAngle(double startT, double endT);
#if DEBUG_COIN
    const SkOpPtT *debugAddT(double t, SkPathOpsDebug::GlitchLog *) const;
#endif
    const SkOpAngle *debugAngle(int id) const;
#if DEBUG_ANGLE
    void debugCheckAngleCoin() const;
#endif
#if DEBUG_COIN
    void debugCheckHealth(SkPathOpsDebug::GlitchLog *) const;
    void debugClearAll(SkPathOpsDebug::GlitchLog *glitches) const;
    void debugClearOne(const SkOpSpan *span, SkPathOpsDebug::GlitchLog *glitches) const;
#endif
    const SkOpCoincidence *debugCoincidence() const;
    SkOpContour *debugContour(int id) const;

    int debugID() const
    {
        return SkDEBUGRELEASE(fID, -1);
    }

    SkOpAngle *debugLastAngle();
#if DEBUG_COIN
    void debugMissingCoincidence(SkPathOpsDebug::GlitchLog *glitches) const;
    void debugMoveMultiples(SkPathOpsDebug::GlitchLog *glitches) const;
    void debugMoveNearby(SkPathOpsDebug::GlitchLog *glitches) const;
#endif
    const SkOpPtT *debugPtT(int id) const;
    void debugReset();
    const SkOpSegment *debugSegment(int id) const;

#if DEBUG_ACTIVE_SPANS
    void debugShowActiveSpans(SkString *str) const;
#endif
#if DEBUG_MARK_DONE
    void debugShowNewWinding(const char *fun, const SkOpSpan *span, int winding);
    void debugShowNewWinding(const char *fun, const SkOpSpan *span, int winding, int oppWinding);
#endif

    const SkOpSpanBase *debugSpan(int id) const;
    void debugValidate() const;

#if DEBUG_COINCIDENCE_ORDER
    void debugResetCoinT() const;
    void debugSetCoinT(int, SkScalar) const;
#endif

#if DEBUG_COIN
    static void DebugClearVisited(const SkOpSpanBase *span);

    bool debugVisited() const
    {
        if (!fDebugVisited) {
            fDebugVisited = true;
            return false;
        }
        return true;
    }
#endif

#if DEBUG_ANGLE
    double distSq(double t, const SkOpAngle *opp) const;
#endif

    bool done() const
    {
        SkOPASSERT(fDoneCount <= fCount);
        return fDoneCount == fCount;
    }

    bool done(const SkOpAngle *angle) const
    {
        return angle->start()->starter(angle->end())->done();
    }

    SkDPoint dPtAtT(double mid) const
    {
        return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
    }

    SkDVector dSlopeAtT(double mid) const
    {
        return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
    }

    void dump() const;
    void dumpAll() const;
    void dumpAngles() const;
    void dumpCoin() const;
    void dumpPts(const char *prefix = "seg") const;
    void dumpPtsInner(const char *prefix = "seg") const;

    const SkOpPtT *existing(double t, const SkOpSegment *opp) const;
    SkOpSegment *findNextOp(SkTDArray<SkOpSpanBase *> *chase, SkOpSpanBase **nextStart, SkOpSpanBase **nextEnd,
        bool *unsortable, bool *simple, SkPathOp op, int xorMiMask, int xorSuMask);
    SkOpSegment *findNextWinding(SkTDArray<SkOpSpanBase *> *chase, SkOpSpanBase **nextStart, SkOpSpanBase **nextEnd,
        bool *unsortable);
    SkOpSegment *findNextXor(SkOpSpanBase **nextStart, SkOpSpanBase **nextEnd, bool *unsortable);
    SkOpSpan *findSortableTop(SkOpContour *);
    SkOpGlobalState *globalState() const;

    const SkOpSpan *head() const
    {
        return &fHead;
    }

    SkOpSpan *head()
    {
        return &fHead;
    }

    void init(SkPoint pts[], SkScalar weight, SkOpContour *parent, SkPath::Verb verb);

    SkOpSpan *insert(SkOpSpan *prev)
    {
        SkOpGlobalState *globalState = this->globalState();
        globalState->setAllocatedOpSpan();
        SkOpSpan *result = globalState->allocator()->make<SkOpSpan>();
        SkOpSpanBase *next = prev->next();
        result->setPrev(prev);
        prev->setNext(result);
        SkDEBUGCODE(result->ptT()->fT = 0);
        result->setNext(next);
        if (next) {
            next->setPrev(result);
        }
        return result;
    }

    bool isClose(double t, const SkOpSegment *opp) const;

    bool isHorizontal() const
    {
        return fBounds.fTop == fBounds.fBottom;
    }

    SkOpSegment *isSimple(SkOpSpanBase **end, int *step) const
    {
        return nextChase(end, step, nullptr, nullptr);
    }

    bool isVertical() const
    {
        return fBounds.fLeft == fBounds.fRight;
    }

    bool isVertical(SkOpSpanBase *start, SkOpSpanBase *end) const
    {
        return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
    }

    bool isXor() const;

    void joinEnds(SkOpSegment *start)
    {
        fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
    }

    const SkPoint &lastPt() const
    {
        return fPts[SkPathOpsVerbToPoints(fVerb)];
    }

    void markAllDone();
    bool markAndChaseDone(SkOpSpanBase *start, SkOpSpanBase *end, SkOpSpanBase **found);
    bool markAndChaseWinding(SkOpSpanBase *start, SkOpSpanBase *end, int winding, SkOpSpanBase **lastPtr);
    bool markAndChaseWinding(SkOpSpanBase *start, SkOpSpanBase *end, int winding, int oppWinding,
        SkOpSpanBase **lastPtr);
    bool markAngle(int maxWinding, int sumWinding, const SkOpAngle *angle, SkOpSpanBase **result);
    bool markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, const SkOpAngle *angle,
        SkOpSpanBase **result);
    void markDone(SkOpSpan *);
    bool markWinding(SkOpSpan *, int winding);
    bool markWinding(SkOpSpan *, int winding, int oppWinding);
    bool match(const SkOpPtT *span, const SkOpSegment *parent, double t, const SkPoint &pt) const;
    bool missingCoincidence();
    bool moveMultiples();
    bool moveNearby();

    SkOpSegment *next() const
    {
        return fNext;
    }

    SkOpSegment *nextChase(SkOpSpanBase **, int *step, SkOpSpan **, SkOpSpanBase **last) const;
    bool operand() const;

    static int OppSign(const SkOpSpanBase *start, const SkOpSpanBase *end)
    {
        int result = start->t() < end->t() ? -start->upCast()->oppValue() : end->upCast()->oppValue();
        return result;
    }

    bool oppXor() const;

    const SkOpSegment *prev() const
    {
        return fPrev;
    }

    SkPoint ptAtT(double mid) const
    {
        return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
    }

    const SkPoint *pts() const
    {
        return fPts;
    }

    bool ptsDisjoint(const SkOpPtT &span, const SkOpPtT &test) const
    {
        SkASSERT(this == span.segment());
        SkASSERT(this == test.segment());
        return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
    }

    bool ptsDisjoint(const SkOpPtT &span, double t, const SkPoint &pt) const
    {
        SkASSERT(this == span.segment());
        return ptsDisjoint(span.fT, span.fPt, t, pt);
    }

    bool ptsDisjoint(double t1, const SkPoint &pt1, double t2, const SkPoint &pt2) const;

    void rayCheck(const SkOpRayHit &base, SkOpRayDir dir, SkOpRayHit **hits, SkArenaAlloc *);
    void release(const SkOpSpan *);

#if DEBUG_COIN
    void resetDebugVisited() const
    {
        fDebugVisited = false;
    }
#endif

    void resetVisited()
    {
        fVisited = false;
    }

    void setContour(SkOpContour *contour)
    {
        fContour = contour;
    }

    void setNext(SkOpSegment *next)
    {
        fNext = next;
    }

    void setPrev(SkOpSegment *prev)
    {
        fPrev = prev;
    }

    void setUpWinding(SkOpSpanBase *start, SkOpSpanBase *end, int *maxWinding, int *sumWinding)
    {
        int deltaSum = SpanSign(start, end);
        *maxWinding = *sumWinding;
        if (*sumWinding == SK_MinS32) {
            return;
        }
        *sumWinding -= deltaSum;
    }

    void setUpWindings(SkOpSpanBase *start, SkOpSpanBase *end, int *sumMiWinding, int *maxWinding, int *sumWinding);
    void setUpWindings(SkOpSpanBase *start, SkOpSpanBase *end, int *sumMiWinding, int *sumSuWinding, int *maxWinding,
        int *sumWinding, int *oppMaxWinding, int *oppSumWinding);
    bool sortAngles();
    bool spansNearby(const SkOpSpanBase *ref, const SkOpSpanBase *check, bool *found) const;

    static int SpanSign(const SkOpSpanBase *start, const SkOpSpanBase *end)
    {
        int result = start->t() < end->t() ? -start->upCast()->windValue() : end->upCast()->windValue();
        return result;
    }

    SkOpAngle *spanToAngle(SkOpSpanBase *start, SkOpSpanBase *end)
    {
        SkASSERT(start != end);
        return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
    }

    bool subDivide(const SkOpSpanBase *start, const SkOpSpanBase *end, SkDCurve *result) const;

    const SkOpSpanBase *tail() const
    {
        return &fTail;
    }

    SkOpSpanBase *tail()
    {
        return &fTail;
    }

    bool testForCoincidence(const SkOpPtT *priorPtT, const SkOpPtT *ptT, const SkOpSpanBase *prior,
        const SkOpSpanBase *spanBase, const SkOpSegment *opp) const;

    SkOpSpan *undoneSpan();
    int updateOppWinding(const SkOpSpanBase *start, const SkOpSpanBase *end) const;
    int updateOppWinding(const SkOpAngle *angle) const;
    int updateOppWindingReverse(const SkOpAngle *angle) const;
    int updateWinding(SkOpSpanBase *start, SkOpSpanBase *end);
    int updateWinding(SkOpAngle *angle);
    int updateWindingReverse(const SkOpAngle *angle);

    static bool UseInnerWinding(int outerWinding, int innerWinding);

    SkPath::Verb verb() const
    {
        return fVerb;
    }

    // look for two different spans that point to the same opposite segment
    bool visited()
    {
        if (!fVisited) {
            fVisited = true;
            return false;
        }
        return true;
    }

    SkScalar weight() const
    {
        return fWeight;
    }

    SkOpSpan *windingSpanAtT(double tHit);
    int windSum(const SkOpAngle *angle) const;

private:
    SkOpSpan fHead;     // the head span always has its t set to zero
    SkOpSpanBase fTail; // the tail span always has its t set to one
    SkOpContour *fContour;
    SkOpSegment *fNext; // forward-only linked list used by contour to walk the segments
    const SkOpSegment *fPrev;
    SkPoint *fPts;           // pointer into array of points owned by edge builder that may be tweaked
    SkPathOpsBounds fBounds; // tight bounds
    SkScalar fWeight;
    int fCount;     // number of spans (one for a non-intersecting segment)
    int fDoneCount; // number of processed spans (zero initially)
    SkPath::Verb fVerb;
    bool fVisited; // used by missing coincidence check
#if DEBUG_COIN
    mutable bool fDebugVisited; // used by debug missing coincidence check
#endif
#if DEBUG_COINCIDENCE_ORDER
    mutable int fDebugBaseIndex;
    mutable SkScalar fDebugBaseMin; // if > 0, the 1st t value in this seg vis-a-vis the ref seg
    mutable SkScalar fDebugBaseMax;
    mutable int fDebugLastIndex;
    mutable SkScalar fDebugLastMin; // if > 0, the last t -- next t val - base has same sign
    mutable SkScalar fDebugLastMax;
#endif
    SkDEBUGCODE(int fID);
};

#endif
